/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-15
 * Time: 20:39
 */
public class Solution {
    public int rob(int[] nums) {
        int length=nums.length;
        if(length==1){
            return nums[0];
        }
//        first记录的是length-1长度的数组的最大值
//        second记录的是length长度的数组的最大值
//        所以后面的判断就是加入该元素还是跳过该元素
//        然后first和second都后移
        int first=nums[0];
        int second=Math.max(nums[0],nums[1]);
        for(int i=2;i<length;i++){
            int temp=second;
            second=Math.max(first+nums[i],second);
            first=temp;
        }
        return second;
    }

    // 更为易懂的代码
    public int robII(int[] nums) {
        int length=nums.length;
        int[][] dp=new int[length][2];
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<length;i++){
            // 不选当前的那么就是前一个的较大值
            dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]);
            // 选当前 那么前面那个肯定不选, 但还是要看与选前面的那么这两种情况中的较大值
            dp[i][1]=Math.max(dp[i-1][0]+nums[i], dp[i-1][1]);
        }
        return Math.max(dp[length-1][0], dp[length-1][1]);
    }
}
